/*
 * @lc app=leetcode.cn id=416 lang=golang
 *
 * [416] 分割等和子集
 */

// @lc code=start
package main

func canPartition(nums []int) bool {
	sum := 0
	for _,v := range nums{
		sum+=v
	}

	if sum%2 == 1{
		return false
	}
	// 背包的大小
	x := sum/2
	// 物品的数量
	n := len(nums)
	dp := make([][]bool,n+1)
	for i,_:=range dp{
		dp[i] = make([]bool,x+1)
	}
	dp[0][0] = true
	for i:=1;i<=n;i++{
		for j:=0;j<=x;j++{
			if j < nums[i-1]{
				dp[i][j] = dp[i-1][j]
			}else{
				dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i-1]]
			}
		}
	}
	return dp[n][x]
	

}

// @lc code=end
